package com.lry.basic.algorithm.matrix;

import java.util.Arrays;
import java.util.PriorityQueue;

public class Matrix {

    public int kthSmallest(int[][] mat, int k) {
        PriorityQueue<PQ> queue = new PriorityQueue();
        int sum=0;
        for(int[] row : mat){
            sum+=row[0];
        }
        int[] indexs = new int[mat[0].length];
        for(int i=0;i<indexs.length;i++){
            indexs[i] = 0;
        }
        queue.offer(new PQ(indexs,sum));

        int num = 0;

        while(num<k){
            PQ pq = queue.poll();
            int i =0;
            while(i<pq.indexs.length){
                int s=0;
                int[] temp = new int[pq.indexs.length];
                boolean f = false;
                for(int j=0;j<temp.length;j++){
                    if(j==i){
                        temp[j] = pq.indexs[j]+1;
                    }else{
                        temp[j] = pq.indexs[j];
                    }
                    if(temp[j]>=mat[0].length){
                        f = true;
                        break;
                    }else{
                        s+=mat[i][temp[j]];
                    }
                }
                if(!f){
                    queue.offer(new PQ(temp,s));
                }
                i++;
            }
            num++;
        }

        return queue.poll().sum;
    }

    public static void main(String[] args) {
        Matrix matrix = new Matrix();
        System.out.println(matrix.kthSmallest(new int[][]{{1, 1, 1}, {2, 4, 6}, {3, 6, 9}}, 3));
    }


    private class PQ implements Comparable{
        public int[] indexs;

        public int sum;

        public PQ(int[] indexs, int sum) {
            this.indexs = indexs;
            this.sum = sum;
        }

        @Override
        public String toString() {
            return "PQ{" +
                    "indexs=" + Arrays.toString(indexs) +
                    ", sum=" + sum +
                    '}';
        }

        @Override
        public int compareTo(Object o) {
            PQ other = (PQ) o;
            return this.sum-other.sum;
        }
    }
}
